/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/combination-sum-ii
   @Language: C++
   @Datetime: 19-06-06 09:54
   */

class Solution {
	void backtrack(vector<int> &cans, int tar, int pos, vector<vector<int> > &vs, vector<int> &v){
		if(tar==0){
			vs.push_back(v);
			return;
		}
		for(int i=pos; i<cans.size() && tar>=cans[i]; ++i){
			if(i!=pos && cans[i]==cans[i-1]) continue;
			v.push_back(cans[i]);
			backtrack(cans,tar-cans[i],i+1,vs,v);
			v.pop_back();
		}
	}
public:
	vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
		vector<vector<int> > vs;
		vector<int> v;
		sort(candidates.begin(),candidates.end());
		backtrack(candidates,target,0,vs,v);
		return vs;
	}
};
